package sample.xiaosong.graphfunc;

import java.util.Collection;
import java.util.HashMap;

/**
 * 并查集结构
 */
public class UnionFindSet {
    // 存储当前节点以及它的父节点
    public HashMap<GraphNode, GraphNode> fatherMap;
    // 存储当前节点的层级(复杂程度)
    public HashMap<GraphNode, Integer> rankMap;

    public UnionFindSet() {
        fatherMap = new HashMap<>();
        rankMap = new HashMap<>();
    }

    /**
     * 初始化并查集
     * 一开始每个节点的父节点均为自己，每个节点的复杂度为1
     * @param graphNodes 图节点列表
     */
    public void initSet(Collection<GraphNode> graphNodes) {
        fatherMap.clear();
        rankMap.clear();
        for (GraphNode node : graphNodes) {
            fatherMap.put(node, node);
            rankMap.put(node, 1);
        }
    }

    /**
     * 查找一个节点的最上层父节点，等价于找二叉树的头节点
     * @param node 图的节点
     * @return 父节点
     */
    public GraphNode findFather(GraphNode node) {
        GraphNode father = fatherMap.get(node);
        if (father != node) {
            father = findFather(father);
        }
        fatherMap.put(node, father);
        return father;
    }

    /**
     * 判断两个节点是否在同一个集合之中   tips：头节点为同一个即在同一个集合
     * @param node1 节点1
     * @param node2 节点2
     * @return TRUE or FALSE
     */
    public boolean isSameSet(GraphNode node1, GraphNode node2) {
        return findFather(node1) == findFather(node2);
    }

    /**
     * 合并两个集合   等价于  合并两个父节点， 合并时将小复杂度合并到大复杂度
     * @param node1 集合1
     * @param node2 集合2
     */
    public void unionSet(GraphNode node1, GraphNode node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        GraphNode father1 = fatherMap.get(node1);
        GraphNode father2 = fatherMap.get(node2);
        if (father1 != father2) {
            Integer rank2 = rankMap.get(node2);
            Integer rank1 = rankMap.get(node1);
            if (rank1 <= rank2) {
                fatherMap.put(father1, father2);
                rankMap.put(father2, rank1 + rank2);
            } else {
                fatherMap.put(father2, father1);
                rankMap.put(father1, rank1 + rank2);
            }
        }
    }
}
